#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
#define x first
#define y second
typedef long long LL;
typedef pair<LL, int> PII;
const int N = 310, M = 5e4 + 10;
int h[N], e[M], ne[M], w1[M], w2[M], w[M], idx;
LL dis[N];
int n, m, s, t;
LL ans;
bool st[N];
void add(int a, int b, int c, int d, int f)
{
	e[idx] = b, ne[idx] = h[a], w[idx] = f, w1[idx] = c, w2[idx] = d, h[a] = idx++;
} 

void dij(int s)
{
	priority_queue < PII, vector<PII>, greater<PII>>q;
	q.push({0,s});
	for (int i = 1; i <= n; i++) {
		dis[i] = 1e15;
	}
	memset(st, 0, sizeof(st));
	dis[s] = 0;
	while (q.size()) {
		PII t = q.top();
		q.pop();
		//cout << "t==" << t << endl;
		int ver = t.y;
		LL distance = t.x;
		if (st[ver])continue;
		st[ver] = 1;
		for (int i = h[ver]; ~i; i = ne[i]) {
			int j = e[i];
			LL t1 = distance % (w1[i] + w2[i]);
			if (w1[i] < w[i])continue;
			if (w1[i] >= w[i]) {
				/*if (t1 <= w1[i]) {
					if (w1[i] - t1 >= w[i]) {
						dis[j] = min(dis[j], distance + w[i]);
					}
					else {
						dis[j] = min(dis[j], distance + w[i] + (w1[i] - t1 + w2[i]));
					}
				}
				else {
					dis[j] = min(dis[j], distance + w[i] + (w2[i] - t1));
				}*/
				if (t1 + w[i] <= w1[i])dis[j] = min(dis[j], distance + w[i]);
				else dis[j] = min(dis[j], distance + w[i] + (w1[i] + w2[i] - t1));
				q.push({ dis[j],j });
				//if (w1[i] - ans >= w[i]) {
				//	dis[j] = distance + w[i];
				//}
				//else {
				//	dis[j] = distance + w[i] + w2[i] + (w1[i] - ans);
				//}
				////cout << "dis[j]==" << dis[j] << endl;
				//q.push({ dis[j],j });
				//ans = w[i];
			}
		}
	}
}
int main()
{
	int z = 1;
	while (cin >> n >> m >> s >> t) {
		idx = 0;
		memset(h, -1, sizeof(h));
		while (m--) {
			int u, v, a, b, z;
			cin >> u >> v >> a >> b >> z;
			add(u, v, a, b, z);
		}
		dij(s);
		cout << "Case " << z++ << ": ";
		if (dis[t] == 1e15)cout << -1 << endl;
		else cout << dis[t] << endl;
	}
	return 0;
}